/*
 * @lc app=leetcode id=488 lang=cpp
 *
 * [488] Zuma Game
 */

// @lc code=start
class Solution {
public:
    unordered_map<string, int> visited;

    int findMinStep(string board, string hand) 
    {
        int res = dfs(board, hand);
        return (res <= hand.size() ? res : -1);
    }

    int dfs(string boa, string hand)
    {
        string cur_state = boa + '-' + hand;
        if (visited.count(cur_state))
            return visited[cur_state];
        int MIN = 100;
        bool find = true;
        string board  = "";
        while (find == true)
        {
            find = false;
            board = "";
            int L = 0;
            while (L < boa.size())            {
                int R = L + 1;
                while (R < boa.size() && boa[L] == boa[R])  R ++;
                if (R - L < 3)      board += boa.substr(L, R - L);
                else                find = true;
                L = R;
            }
            if (board.size() == 0)
            {
                visited[cur_state] = 0;
                return 0;
            }

            boa = board;
        }
        
        for (int i = 0; i < board.size() + 1; i ++)
        {
            for (int j = 0; j < hand.size(); j ++)
            {
                string nxt_hand = hand.substr(0, j) + hand.substr(j+1);
                MIN = min(MIN, 1 + dfs(board.substr(0, i) + hand[j] + board.substr(i),  nxt_hand));
            }
        }
        visited[cur_state] = MIN;
        return MIN;
    }


};
// @lc code=end

